// -*- coding: utf-8 -*-
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-04-03 14:25
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.TREE.segTree;

import org.junit.jupiter.api.Test;

import java.util.TreeMap;


/**
 * 只要不是三重预定就可以
 * 开点线段树 -> 预定的时候寻找包含区间
 * <p>
 * |a--------------b|
 * |c----d|
 * |e--f|
 */
class MyCalendarTwo {
    Node root;

    class Node {
        int start, end;
        Node left, right;
        int val, lazy;

        public Node(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }


    public void pushDown(Node root) {
        if (root == null) {
            return;
        }
        int mid = root.start + ((root.end - root.start) >> 1);
        if (root.left == null) {
            root.left = new Node(root.start, mid);
        }
        if (root.right == null) {
            root.right = new Node(mid + 1, root.end);
        }
        root.left.val += root.lazy;
        root.left.lazy += root.lazy;
        root.right.val += root.lazy;
        root.right.lazy += root.lazy;
        root.lazy = 0;
    }

    public int query(int left, int right) {
        return query(root, left, right);
    }

    private int query(Node root, int left, int right) {
        if (root == null) {
            return 0;
        }
        if (root.start > right || root.end < left) {
            return 0;
        } else if (left <= root.start && right >= root.end) {
            return root.val;
        } else {
            pushDown(root);
            int left_ret = query(root.left, left, right);
            int right_ret = query(root.right, left, right);
            return Math.max(left_ret, right_ret);
        }
    }

    public MyCalendarTwo() {
        root = new Node(0, (int) Math.pow(10, 9) + 2);
    }


    public void update(int left, int right) {
        update(root, left, right);
    }


    private void update(Node node, int left, int right) {
        if (node == null) {
            throw new NullPointerException("NullPointerException!");
        }
        if (left > node.end || right < node.start) {
            // 更新的区间不在当前线段树可以表示的范围: root (10-20) || left - right (30 - 40)
            return;
        } else if (left <= node.start && right >= node.end) {
            // 更新的区间包含的当前节点的区间 -1 - 1e9+10
            node.val++;
            node.lazy++;
            return;
        } else {
            // lazy标签下移操作
            pushDown(node);
            update(node.left, left, right);
            update(node.right, left, right);
            pushup(node);
        }

    }

    private void pushup(Node node) {
        // 更新非叶子节点
        node.val = Math.max(node.left.val, node.right.val);
    }

    public boolean book(int start, int end) {
        return book(root, start, end);
    }

    private boolean book(Node root, int start, int end) {
        int ret = this.query(start, end - 1);
        if (ret >= 2) {
            return false;
        } else {
            this.update(start, end - 1);
            return true;
        }
    }

}


//            TreeMap<Integer, Integer> map = new TreeMap<>();
//
//
//            public MyCalendarTwo() {
//
//            }
//
//            public boolean book(int start, int end) {
//                map.put(start, map.getOrDefault(start, 0) + 1);
//                map.put(end, map.getOrDefault(end, 0) - 1);
//                int cur = 0;
//                for (Integer point : map.keySet()) {
//                    cur += map.get(point);
//                    if (cur > 2) {
//                        map.put(start, map.get(start) - 1);
//                        map.put(end, map.get(end) + 1);
//                        return false;
//                    }
//                }
//                return true;
//            }


